/**
 * @作者 zxy
 * @时间 2023-04-17 17:48
 * @说明
 */
public class Solution {
    public static void main(String[] args) {
        System.out.println(maximumGap(new int[]{3, 6, 1, 9}));
        System.out.println(maximumGap(new int[]{3, 3, 3, 3}));
        System.out.println(maximumGap(new int[]{1, 6, 8, 3, 4, 2, 8}));
        System.out.println(maximumGap(new int[]{1, 5, 9, 5, 3, 1, 2}));
        System.out.println(maximumGap(new int[]{2, 99999999}));
    }

    /**
     * 执行用时：8 ms , 在所有 Java 提交中击败了99.87%的用户
     * 内存消耗：50.8 MB, 在所有 Java 提交中击败了96.87%的用户
     *
     * @param nums
     * @return
     */
    public static int maximumGap(int[] nums) {
        if (nums.length < 2) return 0;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(max, nums[i]);
            min = Math.min(min, nums[i]);
        }
        int interval = (max - min) / nums.length + 1;//桶长度
        int bucketLen = nums.length + 1;
        if (interval == 0) return 0;
        int[] bucketMax = new int[bucketLen];
        int[] bucketMin = new int[bucketLen];
        for (int i = 0; i < bucketLen; i++) {
            bucketMax[i] = Integer.MIN_VALUE;
            bucketMin[i] = Integer.MAX_VALUE;
        }
        for (int i = 0; i < nums.length; i++) {
            int row = (nums[i] - min) / interval;
            bucketMax[row] = Math.max(bucketMax[row], nums[i]);
            bucketMin[row] = Math.min(bucketMin[row], nums[i]);
        }
        int resMax = Integer.MIN_VALUE;
        resMax = Math.max(bucketMin[0] - min, resMax);
        int minIndex = 1, maxIndex = 0;
        while (minIndex < bucketLen) {
            if (bucketMin[minIndex] != Integer.MAX_VALUE && bucketMax[maxIndex] != Integer.MIN_VALUE) {
                resMax = Math.max(bucketMin[minIndex] - bucketMax[maxIndex], resMax);
                maxIndex = minIndex;
                minIndex++;
            } else if (bucketMin[minIndex] == Integer.MAX_VALUE) {
                minIndex++;
            } else if (bucketMax[maxIndex] == Integer.MIN_VALUE) {
                maxIndex--;
            }
        }
        return resMax;
    }
}
